动规(Dynamic Programming)类问题主要求解的步骤: 斐波那契数列\color{Blue}{斐波那契数列}斐波那契数列
1. 划分阶段 斐波那契数列的每一项作为一个阶段\color{Blue}{斐波那契数列的每一项作为一个阶段}斐波那契数列的每一项作为一个阶段
2. 确定状态 第i项的值用数组第i位表示:ai\color{Blue}{第i项的值用数组第i位表示:a_i}第i项的值用数组第i位表示:ai
3. 确定答案所在位置 an\color{Blue}{a_n}an
4. 确定决策并写出状态转移方程式
ai=ai−1+ai−2\color{Blue}{a_i = a_{i-1}+a_{i-2}}ai =ai−1 +ai−2
5. 初始化
a1=a2=1\color{Blue}{a_1 = a_2 = 1}a1 =a2 =1